#include <iostream>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* merge_sort(ListNode* head) {
    if (!head || !head->next) {
        return head;
    }

    // 找到链表的中间节点
    ListNode *slow = head, *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // 分割链表
    ListNode *mid = slow->next;
    slow->next = NULL;

    // 递归排序两个子链表
    ListNode *left = merge_sort(head);
    ListNode *right = merge_sort(mid);

    // 合并两个有序链表
    return merge(left, right);
}

ListNode* merge(ListNode* left, ListNode* right) {
    ListNode dummy(0);
    ListNode *current = &dummy;

    while (left && right) {
        if (left->val < right->val) {
            current->next = left;
            left = left->next;
        } else {
            current->next = right;
            right = right->next;
        }
        current = current->next;
    }

    // 将剩余的节点连接到合并后的链表中
    if (left) {
        current->next = left;
    } else {
        current->next = right;
    }

    return dummy.next;
}

// 辅助函数：打印链表
void print_list(ListNode* head) {
    while (head) {
        std::cout << head->val << " ";
        head = head->next;
    }
    std::cout << std::endl;
}

// 辅助函数：释放链表内存
void delete_list(ListNode* head) {
    while (head) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}
